1. Field of the Invention
This invention relates to digital logic circuits and particularly to programmable logic array semiconductor devices which are capable of performing complex logic functions with a minimum of circuitry.
2. Description of the Prior Art
Programmable Logic Array (PLA) circuitry typically includes a search, or AND, array coupled to a read, or OR, array each including a plurality of programmable semiconductor devices. The arrays are operated to sequentially implement AND or OR logic functions. A basic PLA organization is taught in U.S. Pat. No. 3,702,985 to Proebsting and in U.S. Pat. No. 3,566,153 to Spencer, a modified version of which is illustrated in FIG. 1A, herein. In operation, a plurality of input signals are applied to a series of single input decoders which apply true and complement signals to the AND array, typically implemented with NOR circuits since a NOR circuit performs a logical AND function of complemented input signals. The outputs of the AND array are designated as product terms PT and are applied directly to the inputs of an OR array, also typically implemented with NOR circuits, in order to perform a negative OR logical function of selected product terms. The output signals of the OR array are designated as sum of product terms, or sum terms ST, and are typically stored in output latches to be applied to circuits external to the PLA or can be reapplied to the input decoders for further sequential logic operations. U.S. Pat. No. 3,974,366 to Hebenstreit is of interest as it teaches the use of independent clock inputs, shown in FIG. 1A as C1 and C2, to sequentially control the implementation of the AND and OR functions. The sequential logical operations, excluding external feedback, performed in the basic PLA of FIG. 1A are shown in FIG. 1B. Input signals or their complements are applied to the AND array during C1 time. During C2 time the logical OR array and output circuitry are enabled.
Although a number of useful logic functions can efficiently be implemented using simple PLA organization, complex functions such as binary n-bit counters require excessive array area because of the large number of product terms required. Reduction in the number of product terms necessary to implement a particular logic function can be achieved to some extent by partitioning the input signals into groups of input bits prior to generating the product terms, as taught in U.S. Pat. No. 3,593,317 to Fleisher et al, or by partitioning the input signals into pairs of input bits, as taught in U.S. Pat. No. 3,761,902 to Weinberger. The later technique is known as two-bit partitioning and is extensively used in PLA design as all 16 Boolean logic functions of the input bit can be expressed using only four input lines of the AND array. A significant reduction in the number of product terms can be realized using two-bit partitioning alone. Other area and product term reduction techniques are also known. For example, Exclusive-OR circuits implemented at the outputs of the OR array, as taught in U.S. Pat. No. 3,890,603 to Jones et al may be used to further reduce the number of logic functions executed within the AND and OR arrays of a PLA.
Further PLA reduction techniques include providing logic functions which operate on the product terms before they are provided to the OR array. For example, U.S. Pat. No. 4,032,894 to Williams, teaches the use of selected product term inverters located between the AND and OR arrays. The use of two-bit partitioning of product terms is taught in the article "Multiple Partitioned Programmable Logic Array", by S. B. Greenspan, IBM Technical Disclosure Bulletin, Vol. 19, No. 5, October 1976, pp. 1780-1781. This technique enables an increase in the number of product terms which are available to be applied to the OR array. FIG. 2A represents a block diagram of a basic AND/OR PLA as modified by these techniques and FIG. 2B repesents the sequence of logic operations, including optional operations, which may be executed by such modified PLAs.
Another PLA variation is taught in the article "Array Logic Short Path", by G. J. Robbins, IBM Technical Disclosure Bulletin, Vol. 19, No. 7, December 1976, pp. 2544-2546. Here a capability is provided to provide product terms directly to the PLA output, either bypassing or operating in parallel with the OR array, in order to increase the speed at which some of the array output signals are available.
Yet another PLA variation is taught in U.S. Pat. No. 4,140,967 to Balasubramanian et al, which teaches a merged AND/OR array where alternating columns of a single matrix form both AND and OR sub-arrays, either one of which is capable of being independently driven as a single array under special test conditions. FIG. 3A represents such an array which includes previously described two-bit partitioning of input signals coupled to a matrix including two sets of orthogonal lines. Under normal PLA operating conditions the input decoders drive a first set of horizontal lines which, in combination with the AND sub-array, generate product terms PT1-PT3 on a first set of vertical lines, as in the AND array of a two-array PLA. The vertical product term lines are selectively interconnected directly to overlying ones of a second set of horizontal lines (indicated by an X) which, in combination with the OR sub-array, generate sum terms ST1-ST3 on a second set of vertical lines. The sum terms are then coupled to output logic as in other PLAs. The merged PLA thus operates in the normal AND/OR sequence of directly coupled PLAs as in FIG. 1A. A feature of this merged array is a provision for driving either the AND or the OR sub-array directly by the input decoder, or bit partitioning, circuits so that each of the AND and OR sub-arrays may, be independently tested. A plurality of single-pole single-throw switches SW1 and SW2, responsive to input signals T1 and T2, control the application of the input signals to either the AND sub-array or the OR sub-array. Similar switches are used to couple the output signals to the output logic. FIG. 3B illustrates the sequential logic performed by the merged array under normal and test conditions.
Various other modifications are known to be useful to reduce the area of PLAs such as splitting or folding of input or output lines as taught in U.S. Pat. No. 3,987,287 to Cox et al. Techniques known for increasing the number and/or complexity of logic terms include cross-field partitioning of OR array outputs with input signals as taught in U.S. Pat. No. 3,924,243 to Vermeulen, the use of a plurality of sub-arrays as taught in U.S. Pat. No. 3,975,623 to Weinberger, and the extensive use of double-level interconnection metallurgy to allow more flexible personalization of input/output and feedback lines as taught in U.S. Pat. No. 3,936,812 to Cox et al.
In view of the above improvements, considerable reduction in array area and simplification of array-performed logic is possible making PLA logic implementation competitive in many areas to custom designed logic. In prior art techniques in which the array-performed logic has been decreased; it has been accomplished by increasing the number and complexity of non-array logic performing circuits, sometimes to the point of increasing the total circuit area of the PLA plus supporting circuitry. In addition, highly complex logic implementations such as binary adders require a large number of array-generated logic terms and accordingly are impractical to implement in PLA logic.
The development of multi-functional semiconductor devices such as microprocessor chips requires more logic function be placed on a single semiconductor substrate. Microprocessor systems designers are attempting to meet user requests for 16 and 32 bit processing units. A 32 bit binary adder implemented in a conventional AND/OR PLA using two-bit input partitioning and Exclusive-OR output circuits as described by A. Weinberger in the article "High-Speed Programmable Logic Address", IBM J. Res. Develop., Vol. 23, No. 2, March 1979, pp. 163-178, requires a total of 195 product terms and 196 array columns for a total of 38,220 array bits. Such a PLA requires a considerable area which is impractical to implement on the same semiconductor chip as other required microprocessor logic and memory circuits.